package dongtai;

public class yibaba {
    public static int maxProfit(int k, int[] prices) {
        int n=prices.length;
        if(n==1){
            return 0;
        }
        boolean islow=true;
        for(int m=0;m<n-1;m++){
            if(prices[m]>=prices[m+1]){
                islow=true;
            }else{
                islow=false;
                break;
            }
        }
        if(islow==true){
            return 0;
        }
        int[][] f=new int[n][k+1];
        int[][] g=new int[n][k+1];
        f[0][0]=-prices[0];
        g[0][0]=0;
        for(int j=1;j<k;j++){
            f[0][j]=-0x3f3f3f3f;
            g[0][j]=-0x3f3f3f3f;
        }
        for(int i=1;i<n;i++){
            for(int j=0;j<k+1;j++){
                f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=g[i-1][j];
                if(j-1>=0){
                    g[i][j]=Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
                }
            }
        }
        int max=0;
        for(int j=0;j<k+1;j++){
            if(g[n-1][j]>=max){
                max=g[n-1][j];
            }
        }
        return max;

    }

    public static void main(String[] args) {

    }
}
